<!DOCTYPE html>
<html>

<head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="apple-mobile-web-app-capable" content="yes"/>
<title>E7 - Solution-23航C | pansis.io</title>
<link rel="shortcut icon" href="https://github.pansis.site/favicon.ico">
<link href="https://github.pansis.site/styles/main.css" rel="stylesheet">
<link href="//at.alicdn.com/t/c/font_1678829_b85ccgkdqkr.css" rel="stylesheet">
<link href="//cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet">
<link rel="alternate" type="application/rss+xml" title="pansis.io » Feed" href="https://github.pansis.site/atom.xml">
        <meta name="description" content="E7 - Solution
A 七擒孟获



难度
考点




1
输出字符画



示例代码
#include &lt;stdio.h&gt;
int main()
{
	printf(&quot;__________________..." />
        <meta name="keywords" content="23航C" />
        <!-- OG -->
        <meta property="og:locale" content="zh_CN">
        <meta property="og:title" content="E7 - Solution-23航C" />
        <meta property="og:type" content="article" />
        <meta property="og:description" content="E7 - Solution
A 七擒孟获



难度
考点




1
输出字符画



示例代码
#include &amp;lt;stdio.h&amp;gt;
int main()
{
	printf(&amp;quot;__________________...">
        <meta property="og:url" content="https://github.pansis.site/post/E7 - Solution-23航C/" />
        <meta property="og:site_name" content="pansis.io">
        <meta property="og:updated_time" content="2024-05-17">
        <meta property="og:image" content="" />
        <meta property="og:image:secure_url" content="">
        <meta property="og:image:alt" content="E7 - Solution-23航C">
        <!-- Twitter (post.ejs) -->
        <meta name="twitter:card" content="summary_large_image">
        <meta name="twitter:title" content="E7 - Solution-23航C">
        <meta name="twitter:description" content="E7 - Solution
A 七擒孟获



难度
考点




1
输出字符画



示例代码
#include &amp;lt;stdio.h&amp;gt;
int main()
{
	printf(&amp;quot;__________________...">
        <!-- <meta name="twitter:site" content="@WBoy0609">
        <meta name="twitter:creator" content="@WBoy0609"> -->
        <meta name="twitter:image" content="">
</head>

<body>
    <div class="main animated">
        <div class="header animated fadeInDown">
    <div class="site_title_container">
        <div class="site_title">
            <a href="https://github.pansis.site">pansis.io</a>
        </div>
    </div>
    <div class="my_socials">
        
            
        
            
        
            
        
            
        
            
        
            
        
            
        
        <a href="https://github.pansis.site/atom.xml" title="rss" target="_blank"><i class="iconfont icon-rss"></i></a>
    </div>
</div>

    <div class="header_menu">
        
            
                <a href="/" class="menu">首页</a>
            
        
            
                <a href="/tag/GWAaV2nvk/" class="menu">程序设计课程</a>
            
        
            
                <a href="/tag/24hangc" class="menu">比赛</a>
            
        
            
                <a href="/tag/L7r9STb75/" class="menu">Python教程</a>
            
        
            
                <a href="/tags" class="menu">分类</a>
            
        
        <div class="gridea-search-div">
            <form id="gridea-search-form" action="https://github.pansis.site/search/">
                <input class="gridea-search-input" autocomplete="off" spellcheck="false" name="q"/>
            </form>
        </div>
    </div>

            <div class="autopagerize_page_element">
                <div class="content">
                    <div class="post_page">
                        <div class="post animated fadeInDown">
                            <div class="post_title post_detail_title">
                                <h2>
                                    E7 - Solution-23航C
                                </h2>
                                <span class="article-info">
                                    2024-05-17, 7109 words, 35 min read
                                </span>
                            </div>
                            <div class="post_content markdown">
                                <p class="md_block">
                                    <span class="md_line md_line_start md_line_end">
                                        <h1 id="e7-solution">E7 - Solution</h1>
<h2 id="a-七擒孟获"><code>A</code> 七擒孟获</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>输出字符画</td>
</tr>
</tbody>
</table>
<h3 id="示例代码">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	printf(&quot;_____________________\n&quot;
	       &quot;|         oxx       |\n&quot;
	       &quot;|   o      ox x x   |\n&quot;
	       &quot;|  xo     oooxxxoxx |\n&quot;
	       &quot;|   o ooooxxoooooxxx|\n&quot;
	       &quot;|  xoxoxxxxxxooo oxo|\n&quot;
	       &quot;|  oxooxxooxxoox oxo|\n&quot;
	       &quot;|  oxxxxoooxoxxooooo|\n&quot;
	       &quot;|  ox   xo ooxxxooxo|\n&quot;
	       &quot;|oooxxx xoo oxoxxxxx|\n&quot;
	       &quot;|oxoxoxxoo ooooxxxox|\n&quot;
	       &quot;|oxooox xooxxooxoooo|\n&quot;
	       &quot;|xxxxoox xxxoxooo  o|\n&quot;
	       &quot;|x xoox   xx xxxxoox|\n&quot;
	       &quot;| xooox  xox    xoxx|\n&quot;
	       &quot;|x xoxxxxxoox  oxxx |\n&quot;
	       &quot;| xxooooxooox ox    |\n&quot;
	       &quot;|xxxo oxo oxoooox   |\n&quot;
	       &quot;|oxoo     oxox  x   |\n&quot;
	       &quot;|ooo      oxxxxxx   |\n&quot;
	       &quot;^^^^^^^^^^^^^^^^^^^^^\n&quot;);
	return 0;
}
</code></pre>
<h2 id="b-平均值和不确定度"><code>B</code> 平均值和不确定度</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>浮点数</td>
</tr>
</tbody>
</table>
<h3 id="题目分析">题目分析</h3>
<p>代入公式计算即可，注意计算除法的时候不要出现“整型除以整型”的错误。</p>
<h3 id="示例代码-1">示例代码 1</h3>
<pre><code class="language-c">#include&lt;stdio.h&gt;
#include&lt;math.h&gt;
int main() {
	double x[1005];
	int n = 1;

	while (scanf(&quot;%lf&quot;, &amp;x[n]) != EOF) {
		n++;
	}
	n = n - 1;
	double avg = 0;
	for (int i = 1; i &lt;= n; i++) {
		avg += x[i];
	}
	avg /= n;
	printf(&quot;%.4f &quot;, avg);
	double sum = 0;
	for (int i = 1; i &lt;= n; i++) {
		sum += (1.0 / n / (n - 1) * (x[i] - avg) * (x[i] - avg));
	}
	printf(&quot;%.4f&quot;, sqrt(sum));
}
</code></pre>
<h3 id="示例代码-2">示例代码 2</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;math.h&gt;
int main()
{
	double x, avg = 0.0, ua = 0.0;
	int n = 0;
	while (scanf(&quot;%lf&quot;, &amp;x) != EOF)
	{
		avg += x;
		ua += x * x;
		n++;
	}
	avg /= n;
	ua = sqrt((ua / n - avg * avg) / (n - 1));
	printf(&quot;%.4lf %.4lf&quot;, avg, ua);
	return 0;
}
</code></pre>
<h2 id="c-简单电路"><code>C</code> 简单电路</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>2</td>
<td>结构体、最大公约数</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-2">题目分析</h3>
<p>按照题意所给算式计算即可，注意分数的约分和分母为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 的情况即可，也可以使用结构体表示分数。</p>
<h3 id="示例代码-1-2">示例代码 1</h3>
<pre><code class="language-cpp">#include&lt;stdio.h&gt;
int gcd(int x, int y)
{
	if(x == 0) return y;
	return gcd(y % x, x);
}
int main()
{
	int t, op, a, b;
	scanf(&quot;%d&quot;, &amp;t);
	while(t--)
	{
		scanf(&quot;%d %d %d&quot;, &amp;op, &amp;a, &amp;b);
		if(op == 0)
			printf(&quot;%d\n&quot;, a + b);
		else
		{
			int x = a * b, y = a + b, g;
			g = gcd(x, y);
			x = x / g, y = y / g;
			if(y == 1)
				printf(&quot;%d\n&quot;, x);
			else
				printf(&quot;%d %d\n&quot;, x, y);
		}
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-2">示例代码 2</h3>
<pre><code class="language-cpp">#include&lt;stdio.h&gt;
struct Quotient // 分数结构体
{
	int p, q;
};
int gcd(int x, int y)
{
	if(x == 0)
	{
		return y;
	}
	return gcd(y % x, x);
}
struct Quotient red(struct Quotient x) //分数约分
{
	struct Quotient ans;
	int g = gcd(x.p, x.q);
	ans.p = x.p / g, ans.q = x.q / g;
	return ans;
}
struct Quotient add(struct Quotient x, struct Quotient y) //分数相加
{
	struct Quotient ans;
	ans.p = x.p * y.q + x.q * y.p;
	ans.q = x.q * y.q;
	ans = red(ans);
	return ans;
}
struct Quotient mul(struct Quotient x, struct Quotient y) //分数相乘
{
	struct Quotient ans;
	ans.p = x.p * y.p;
	ans.q = x.q * y.q;
	ans = red(ans);
	return ans;
}
struct Quotient div(struct Quotient x, struct Quotient y) //分数相除
{
	struct Quotient ans;
	ans.p = x.p * y.q;
	ans.q = x.q * y.p;
	ans = red(ans);
	return ans;
}
void print(struct Quotient x) //输出分数
{
	if(x.q == 1)
	{
		printf(&quot;%d\n&quot;, x.p);
	}
	else
	{
		printf(&quot;%d %d\n&quot;, x.p, x.q);
	}
}
int main()
{
	int t, op, a, b;
	scanf(&quot;%d&quot;, &amp;t);
	while(t--)
	{
		struct Quotient a, b, base;
		scanf(&quot;%d %d %d&quot;, &amp;op, &amp;a.p, &amp;b.p);
		a.q = 1, b.q = 1;
		base.p = 1, base.q = 1;
		if(op == 0)
		{
			print(add(a, b));
		}
		else
		{
			print(div(base, add(div(base, a), div(base, b))));
		}
	}
	return 0;
}
</code></pre>
<h2 id="d-简单神奇的四元数"><code>D</code> 简单神奇的四元数</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>3</td>
<td>结构体，函数传参</td>
</tr>
</tbody>
</table>
<h3 id="题意分析">题意分析</h3>
<p>两个四元数的加法定义如下：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><mi>a</mi><mo>+</mo><mi>b</mi><mi>i</mi><mo>+</mo><mi>c</mi><mi>j</mi><mo>+</mo><mi>d</mi><mi>k</mi><mo>)</mo><mo>+</mo><mo>(</mo><mi>w</mi><mo>+</mo><mi>x</mi><mi>i</mi><mo>+</mo><mi>y</mi><mi>j</mi><mo>+</mo><mi>z</mi><mi>k</mi><mo>)</mo><mspace linebreak="newline"></mspace><mo>=</mo><mo>(</mo><mi>a</mi><mo>+</mo><mi>w</mi><mo>)</mo><mo>+</mo><mo>(</mo><mi>b</mi><mo>+</mo><mi>x</mi><mo>)</mo><mi>i</mi><mo>+</mo><mo>(</mo><mi>c</mi><mo>+</mo><mi>y</mi><mo>)</mo><mi>j</mi><mo>+</mo><mo>(</mo><mi>d</mi><mo>+</mo><mi>z</mi><mo>)</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">(a+bi+cj+dk)+(w+xi+yj+zk)\\=(a+w)+(b+x)i+(c+y)j+(d+z)k
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.74285em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">x</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.36687em;vertical-align:0em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">x</span><span class="mclose">)</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">c</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mclose">)</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">d</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mclose">)</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span></span></p>
<p>两个四元数的乘法定义如下：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><mi>a</mi><mo>+</mo><mi>b</mi><mi>i</mi><mo>+</mo><mi>c</mi><mi>j</mi><mo>+</mo><mi>d</mi><mi>k</mi><mo>)</mo><mo>(</mo><mi>w</mi><mo>+</mo><mi>x</mi><mi>i</mi><mo>+</mo><mi>y</mi><mi>j</mi><mo>+</mo><mi>z</mi><mi>k</mi><mo>)</mo><mspace linebreak="newline"></mspace><mo>=</mo><mo>(</mo><mi>a</mi><mi>w</mi><mo>−</mo><mi>b</mi><mi>x</mi><mo>−</mo><mi>c</mi><mi>y</mi><mo>−</mo><mi>d</mi><mi>z</mi><mo>)</mo><mspace linebreak="newline"></mspace><mo>+</mo><mo>(</mo><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>w</mi><mo>+</mo><mi>c</mi><mi>z</mi><mo>−</mo><mi>d</mi><mi>y</mi><mo>)</mo><mi>i</mi><mspace linebreak="newline"></mspace><mo>+</mo><mo>(</mo><mi>a</mi><mi>y</mi><mo>−</mo><mi>b</mi><mi>z</mi><mo>+</mo><mi>c</mi><mi>w</mi><mo>+</mo><mi>d</mi><mi>x</mi><mo>)</mo><mi>j</mi><mspace linebreak="newline"></mspace><mo>+</mo><mo>(</mo><mi>a</mi><mi>z</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>−</mo><mi>c</mi><mi>x</mi><mo>+</mo><mi>d</mi><mi>w</mi><mo>)</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">(a+bi+cj+dk)(w+xi+yj+zk)\\=(aw-bx-cy-dz)\\+(ax+bw+cz-dy)i\\+(ay-bz+cw+dx)j\\+(az+by-cx+dw)k
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.74285em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">x</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.36687em;vertical-align:0em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.7777700000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mclose">)</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault">x</span><span class="mclose">)</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">a</span><span class="mord mathdefault" style="margin-right:0.04398em;">z</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">b</span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mclose">)</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span></span></p>
<p>定义四元数结构体：</p>
<pre><code class="language-c">struct quaternion{
	int w, x, y, z;
};
</code></pre>
<p>定义四元数的加法函数和乘法函数：</p>
<pre><code class="language-c">struct quaternion sum(struct quaternion p, struct quaternion q)
{
	struct quaternion ans =
	{
		p.w + q.w,
		p.x + q.x,
		p.y + q.y,
		p.z + q.z
	};
	return ans;
}
struct quaternion prod(struct quaternion p, struct quaternion q)
{
	struct quaternion ans =
	{
		p.w * q.w - p.x * q.x - p.y * q.y - p.z * q.z,
		p.w * q.x + p.x * q.w + p.y * q.z - p.z * q.y,
		p.w * q.y - p.x * q.z + p.y * q.w + p.z * q.x,
		p.w * q.z + p.x * q.y - p.y * q.x + p.z * q.w
	};
	return ans;
}
</code></pre>
<p>计算算式使用上面两个函数即可。</p>
<p>运用结构体可以使函数一次返回多个值，方便传递参数。</p>
<h3 id="示例代码-2">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
struct quaternion
{
	int w, x, y, z;
} a[10];
struct quaternion sum(struct quaternion p, struct quaternion q) //四元数加法函数，计算并返回p+q
{
	struct quaternion ans =
	{
		p.w + q.w,
		p.x + q.x,
		p.y + q.y,
		p.z + q.z
	};
	return ans;
}
struct quaternion prod(struct quaternion p, struct quaternion q) //四元数乘法函数，计算并返回pq
{
	struct quaternion ans =
	{
		p.w * q.w - p.x * q.x - p.y * q.y - p.z * q.z,
		p.w * q.x + p.x * q.w + p.y * q.z - p.z * q.y,
		p.w * q.y - p.x * q.z + p.y * q.w + p.z * q.x,
		p.w * q.z + p.x * q.y - p.y * q.x + p.z * q.w
	};
	return ans;
}
void print(struct quaternion p) //输出四元数p的函数
{
	printf(&quot;%d %d %d %d\n&quot;, p.w, p.x, p.y, p.z);
}
int main()
{
	for(int i = 1; i &lt;= 8; ++i)
		scanf(&quot;%d%d%d%d&quot;, &amp;a[i].w, &amp;a[i].x, &amp;a[i].y, &amp;a[i].z);
    //计算并输出a7+a1
	print(sum(a[7], a[1]));
    //计算并输出a3+a5
	print(prod(a[3], a[5]));
    //计算并输出a4a2+a5a3
	print(sum(prod(a[4], a[2]), prod(a[5], a[3])));
    //计算并输出a4a2a6
	print(prod(prod(a[4], a[2]), a[6]));
    //计算并输出a8a3(a1a7+a6)a8
	print(prod(prod(a[8], a[3]), prod(sum(prod(a[1], a[7]), a[6]), a[8])));
	return 0;
}
</code></pre>
<h2 id="e-动态分配内存与指针数组"><code>E</code> 动态分配内存与指针数组</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4</td>
<td>malloc，指针数组</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-3">题目分析</h3>
<p>下面为大家提供两种思路：</p>
<p>第一种思路：</p>
<p>如 Hint 所说，存储所有字符串，如果直接开二维数组的话，第二个维度太大许多空间就被浪费了（对于这道题会 MLE）；第二维开的太小的话又存不下最长的字符串，所以我们想到用 malloc 为每个字符串动态分配空间。我们要开一个指针数组指向每个字符串，数组中的每个元素指向了一个长度不定的字符数组。有一些细节问题需要注意：申请的空间要比 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mi>e</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">len</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">e</span><span class="mord mathdefault">n</span></span></span></span> 多一位，用来存字符串最后的 <code>\0</code>；空格（用 gets 读入）和换行（第一行后面的）的处理；字符串的交换（交换两个指针实现）。</p>
<p>第二种思路：</p>
<p>实际上我们也可以不使用 malloc，可以连续地读入一个又一个字符串（别忘了字符串是以最后的空字符为界的）存储在一个足够大的一维字符数组中，每次只需要记录每个字符串的起始地址。具体实现上来说还是开一个指针数组，每用读入一个字符串之后，就将其首地址赋给对应的指针元素。然后下一次读入，从与前一个字符串没有重叠的位置开始存储（不重叠包括前一个字符串最后的空字符，字符串以空字符为界，如果覆盖掉这个空字符就没法正确地分离出字符串了），再重复上述过程。最后的交换过程还是通过交换两个指针实现。</p>
<p>具体实现参考下面的实例代码，示例一对应着思路一，示例二对应着思路二。</p>
<h3 id="示例代码-1-3">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
char *s[10005];
char str[1005];
int main()
{
	int n, m;
	scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
	getchar(); // 吃掉换行符
	for(int i = 1; i &lt;= n; i++) // 读入每个字符串
	{
		gets(str);
		int len = strlen(str);
		s[i] = (char*)malloc((len + 1) * sizeof(char)); // 多开一位存'\0'，sizeof(char) 实际上就是 1
		strcpy(s[i], str);
	}
	for(int i = 1; i &lt;= m; i++) // 交换字符串
	{
		int u, v;
		scanf(&quot;%d%d&quot;, &amp;u, &amp;v);
		char *x = s[u];
		s[u] = s[v];
		s[v] = x;
	}
	for(int i = 1; i &lt;= n; i++)
	{
		puts(s[i]);
		free(s[i]); //有借有还
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-3">示例代码 2</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
char str[450000]; // 用来线性地保存所有字符串
char *s[10005];
int main()
{
	int n, m;
	char *p = str;
	scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
	getchar();
// 处理换行符
	for(int i = 1; i &lt;= n; i++)
	{
		s[i] = gets(p); // 读入并记录每个字符串的起始位置
		p += strlen(p) + 1; // 指针向后移动，别忘了空字符，所以是 len + 1
	}
	for(int i = 1; i &lt;= m; i++)
	{
		int u, v;
		scanf(&quot;%d%d&quot;, &amp;u, &amp;v);
		char *x = s[u];
		s[u] = s[v];
		s[v] = x;
	}
	for(int i = 1; i &lt;= n; i++)
		puts(s[i]);
	return 0;
}
</code></pre>
<h2 id="f-这是第几个后缀"><code>F</code> 这是第几个后缀？</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4</td>
<td>qsort，指针数组，字符串</td>
</tr>
</tbody>
</table>
<h3 id="题意分析-2">题意分析</h3>
<p>​	字符串以 '\0' 作为结尾， <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mi>t</mi><mi>r</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">str[i]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">s</span><span class="mord mathdefault">t</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span></span></span></span> 的地址就代表了 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mi>t</mi><mi>r</mi></mrow><annotation encoding="application/x-tex">str</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">s</span><span class="mord mathdefault">t</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 去掉前 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个字符后的剩下的后缀。可以建立存储 <code>char *</code> 类型的指针数组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span></span></span></span> ， <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">p[i]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">p</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span></span></span></span> 指向 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mi>t</mi><mi>r</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">str[i]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">s</span><span class="mord mathdefault">t</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span></span></span></span> 的地址，然后对数组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span></span></span></span> 用 <code>qsort</code> 排序即可。注意比较函数函数的写法。</p>
<p>​	也可以用 <code>int</code> 类型的数组代替数组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span></span></span></span> ，比较时通过下标访问地址，具体实现见示例代码。</p>
<h3 id="示例代码-1指针数组">示例代码 1：指针数组</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
char s[10005];
char *p[10005];
int cmp(const void *e1, const void *e2)
{
	return strcmp(*(char**)e1, *(char**)e2);
}
int main()
{
	gets(s);
	int len = strlen(s);
	for(int i = 0; i &lt; len; ++i)
		p[i] = s + i;
	qsort(p, len, sizeof(char *), cmp);
	int t;
	scanf(&quot;%d&quot;, &amp;t);
	puts(p[--t]); //由于p是从0开始计数，第t小的应该是p[t-1]
	return 0;
}
</code></pre>
<h3 id="示例代码-2整型数组">示例代码 2：整型数组</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
char s[10006];
int x[10006];
int cmp(const void *aa, const void *bb)
{
	int a = *(int*)aa, b = *(int*)bb;
	return strcmp(s + a, s + b);
}
int main()
{
	int n, len;
	scanf(&quot;%s&quot;, s);
	scanf(&quot;%d&quot;, &amp;n);
	len = strlen(s);
	for (int i = 0; i &lt; len; i++)
		x[i] = i;
	qsort(x, len, sizeof(int), cmp);
	printf(&quot;%s&quot;, s + x[n - 1]);
}
</code></pre>
<h2 id="g-算一个矩阵的幂"><code>G</code> 算一个矩阵的幂</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4~5</td>
<td>二维数组，矩阵乘法</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-4">题目分析</h3>
<p>题目中给出了三个矩阵A，B，C，还有一个整数p，需要我们实现矩阵的乘法，加法和幂，三种运算。</p>
<h4 id="思路一结构体">思路一：结构体</h4>
<p>利用结构体存储矩阵，注意二维数组 <code>data</code> 的大小要足够大。</p>
<pre><code class="language-c">typedef struct _Matrix{
	int row;
	int col;
	int data[10][10];
} Matrix;
</code></pre>
<p>实现加法、乘法、幂次函数，函数声明如下：</p>
<pre><code class="language-c">Matrix sum(Matrix a, Matrix b);
Matrix prod(Matrix a, Matrix b);
Matrix power(Matrix a, int n);
</code></pre>
<p>具体见示例代码。</p>
<h4 id="思路二二维数组函数传参">思路二：二维数组函数传参</h4>
<p>我们首先需要计算矩阵A和B相乘的结果。注意，在计算矩阵相乘时，必须将计算的结果存储在一个新的数组<code>tmp</code>之中，这意味着A和B必须是<strong>只读</strong>的。若将中间的计算结果写到A或B中，就会出现计算错误，这与矩阵计算乘法的方法有关，因为被覆盖掉的原来的值后续还需要使用。</p>
<p>接下来加上一个矩阵C，这里可以将C直接加到相乘的结果<code>tmp</code>中，加法不需要考虑覆盖的问题，因为被覆盖掉的<code>tmp</code>中的元素之后就不会用到了。</p>
<p>最后是计算矩阵的幂次，本质是对矩阵做乘法，与A、B矩阵的乘法操作相同，重复操作可用函数实现。</p>
<h3 id="示例代码-1-4">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
typedef struct _Matrix{
	int row;
	int col;
	int data[10][10];
} Matrix;
Matrix prod(Matrix a, Matrix b) {
	Matrix c = {};
	c.row = a.row;
	c.col = b.col;
	for(int i = 0; i &lt; a.row; i++)
		for(int j = 0; j &lt; b.col; j++)
			for(int k = 0; k &lt; a.col; k++)
				c.data[i][j] += a.data[i][k] * b.data[k][j];
	return c;
}
Matrix sum(Matrix a, Matrix b) {
	Matrix c = {};
	c.row = a.row;
	c.col = a.col;
	for(int i = 0; i &lt; a.row; i++)
		for(int j = 0; j &lt; a.col; j++)
			c.data[i][j] = a.data[i][j] + b.data[i][j];
	return c;
}
Matrix power(Matrix a, int n) {
	Matrix c = a;
	for(int i = 1; i &lt; n; i++)
		c = prod(c, a);
	return c;
}
int main()
{
	int m, n, p;
	scanf(&quot;%d %d %d&quot;, &amp;m, &amp;n, &amp;p);
	Matrix A = {m, n}, B = {n, m}, C = {m, m};
	// input A
	for(int i = 0; i &lt; m; i++)
		for(int j = 0; j &lt; n; j++)
			scanf(&quot;%d&quot;, &amp;A.data[i][j]);
	// input B
	for(int i = 0; i &lt; m; i++)
		for(int j = 0; j &lt; n; j++)
			scanf(&quot;%d&quot;, &amp;B.data[j][i]);
	// input C
	for(int i = 0; i &lt; m; i++)
		for(int j = 0; j &lt; m; j++)
			scanf(&quot;%d&quot;, &amp;C.data[i][j]);
	// Calculate
	Matrix ans = power(sum(prod(A, B), C), p);
    // Output ans
	for(int i = 0; i &lt; m; i++) {
		for(int j = 0; j &lt; m; j++)
			printf(&quot;%d &quot;, ans.data[i][j]);
		puts(&quot;&quot;);
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-4">示例代码 2</h3>
<pre><code class="language-C">#include &lt;stdio.h&gt;

//矩阵的乘法
void mult(int ans[][11], int A[][11], int B[][11], int m, int n)
{
    int i, j, k;
    int sum = 0;
    //中间使用tmp矩阵暂存相乘结果。
    //若ans就是A或B，tmp能够避免A或B中元素被覆盖的问题。
    int tmp[11][11];
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= m; j++)
        {
            sum = 0;
            for (k = 1; k &lt;= n; k++)
            {
                sum += A[i][k] * B[k][j];
            }
            tmp[i][j] = sum;
        }
    }

    //将tmp中暂存的结果赋值进入ans中
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= m; j++)
        {
            ans[i][j] = tmp[i][j];
        }
    }
}

//矩阵加法
void add(int ans[][11], int A[][11], int B[][11], int m, int n)
{
    int i, j;
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= n; j++)
        {
            ans[i][j] = A[i][j] + B[i][j];
        }
    }
}

int main()
{
    int m, n, p;
    int A[11][11], B[11][11], C[11][11], tmp[11][11], ans[11][11];
    scanf(&quot;%d%d%d&quot;, &amp;m, &amp;n, &amp;p);
    int i, j;

    //输入A矩阵
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= n; j++)
        {
            scanf(&quot;%d&quot;, &amp;A[i][j]);
        }
    }

    //输入B矩阵
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= n; j++)
        {
            scanf(&quot;%d&quot;, &amp;B[j][i]); //输入时完成对B的转置操作
        }
    }

    //输入C矩阵
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= m; j++)
        {
            scanf(&quot;%d&quot;, &amp;C[i][j]);
        }
    }

    //将A和B相乘，结果存入tmp
    mult(tmp, A, B, m, n);

    //tmp与C相加，结果存入tmp
    add(tmp, tmp, C, m, m);

    //将相加结果复制到ans中，为矩阵幂次计算做准备
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= m; j++)
        {
            ans[i][j] = tmp[i][j];
        }
    }

    //循环p-1次
    for (i = 1; i &lt; p; i++)
    {
        mult(ans, ans, tmp, m, m);
    }

    //输出结果
    for (i = 1; i &lt;= m; i++)
    {
        for (j = 1; j &lt;= m; j++)
        {
            printf(&quot;%d &quot;, ans[i][j]);
        }
        printf(&quot;\n&quot;);
    }
    return 0;
}
</code></pre>
<h2 id="h-哪吒的区间合并"><code>H</code> 哪吒的区间合并</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5</td>
<td>结构体，数组，qsort</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-5">题目分析</h3>
<p>​	基本思路是将区间按左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。排序后遍历每个区间，根据右端点情况进行合并并输出结果。具体实现思路如下：</p>
<p>​	利用结构体数组或二维数组记录所有区间，每个区间共四个元素，分别记录左端点大小、右端点大小、左端点开闭性、右端点开闭性，其中开闭性可以用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 表示闭， <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span> 表示开。</p>
<p>​	全部读入后，先对所有区间进行排序，排序规则：按区间左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。</p>
<p>​	然后遍历每一个区间，用一个临时结构体或一维数组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 记录当前合并的结果，初始化 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 为当前遍历到的区间，然后继续遍历开始合并区间。只有当前区间左端点小于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 右端点，或当前区间左端点等于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 右端点且不全为开区间时，才能合并。</p>
<p>​	在合并时，如果当前区间右端点大于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> ，更新 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 的右端点及其开闭性为当前区间的右端点及其开闭性；如果当前区间右端点等于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> ，更新 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 的右端点的开闭性，当前区间右端点开闭性和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 中有一者为闭则更新 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 右端点开闭性为闭，否则为开；如果当前区间右端点小于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> ，则不应改变 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 。</p>
<p>​	无法再进行合并时，输出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span> 记录的区间合并结果，然后继续遍历二维数组，直至结束。</p>
<h3 id="示例代码-1-结构体数组">示例代码 1 - 结构体数组</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
typedef struct _Interval
{
	int left, right; //存储左右端点大小
	int loc, roc; //表示左/右端点开闭性，0-开，1-闭
} Interval, *pInterval;
int cmp(const void *e1, const void *e2) //按区间左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。
{
	pInterval p = (pInterval)e1, q = (pInterval)e2;
	if(p-&gt;left &gt; q-&gt;left) return 1;
	if(p-&gt;left &lt; q-&gt;left) return -1;
	if(p-&gt;loc &lt; q-&gt;loc) return 1;
	if(p-&gt;loc &gt; q-&gt;loc) return -1;
	return 0;
}
Interval a[500005];
int main()
{
	int n = 0; //记录输入的区间数量
	char l, r;
	while(~scanf(&quot; %c%d,%d%c&quot;, &amp;l, &amp;a[n].left, &amp;a[n].right, &amp;r))
	{
		a[n].loc = l == '[' ? 1 : 0;
		a[n].roc = r == ']' ? 1 : 0;
		++n;
	}
	qsort(a, n, sizeof(Interval), cmp); //按区间左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。
	for(int i = 0; i &lt; n;)
	{
		Interval t = a[i]; //记录本次合并结果，初始化t为本次合并的最初区间
		//只有区间a[i]左端点小于t右端点，或区间a[i]左端点等于t右端点且不全为开区间时，才能合并
		for(++i; i &lt; n &amp;&amp; (a[i].left &lt; t.right || (a[i].left == t.right &amp;&amp; (a[i].loc | t.roc))); ++i) //至少一个闭时a[i].loc|t.roc为1，若均为开则为0
		{
			if(a[i].right &gt; t.right) //a[i]右端点大于t，更新t右端点及其开闭性为a[i]右端点及其开闭性
				t.right = a[i].right, t.roc = a[i].roc;
			else if(a[i].right == t.right) //a[i]右端点等于t，更新t右端点的开闭性（a[i]和t中有一者为闭则更新t右端点开闭性为闭，否则为开）
				t.roc |= a[i].roc;
			//若a[i]右端点小于t，则不需要改变t
		}
		printf(&quot;%c%d,%d%c\n&quot;, t.loc ? '[' : '(', t.left, t.right, t.roc ? ']' : ')'); //输出本次合并结果
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-二维数组">示例代码 2 - 二维数组</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
int cmp(const void *e1, const void *e2) //按区间左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。
{
	int *p = (int *)e1;
	int *q = (int *)e2;
	if(p[0] &gt; q[0]) return 1;
	else if(p[0] &lt; q[0]) return -1;
	else if(p[2] &lt; q[2]) return 1;
	else if(p[2] &gt; q[2]) return -1;
	else return 0;
}
/*
二维数组a记录输入区间
每行：
0-左端点大小
1-右端点大小
2-左端点开闭性，1表示闭，0表示开
3-右端点开闭性，1表示闭，0表示开
*/
int a[500005][4];
int main()
{
	int n = 0; //记录输入的区间数量
	char l, r;
	while(~scanf(&quot;%c%d,%d%c &quot;, &amp;l, &amp;a[n][0], &amp;a[n][1], &amp;r))
	{
		a[n][2] = l == '[' ? 1 : 0;
		a[n][3] = r == ']' ? 1 : 0;
		++n;
	}
	qsort(a, n, sizeof(a[0]), cmp); //按区间左端点大小升序排序，当左端点相同时，闭区间在前，开区间在后。
	for(int i = 0; i &lt; n;)
	{
		int t[4] = {a[i][0], a[i][1], a[i][2], a[i][3]}; //记录本次合并结果，初始化t为本次合并的最初区间 
		//只有区间a[i]左端点小于t右端点，或区间a[i]左端点等于t右端点且不全为开区间，才能合并
		for(++i; i &lt; n &amp;&amp; (a[i][0] &lt; t[1] || (a[i][0] == t[1] &amp;&amp; (a[i][2] | t[3]))); ++i) //至少一个闭时a[i][2]|t[3]为1，若均为开则为0
		{
			if(a[i][1] &gt; t[1]) //a[i]右端点大于t，更新t右端点及其开闭性为a[i]右端点及其开闭性
				t[1] = a[i][1], t[3] = a[i][3];
			else if(a[i][1] == t[1]) //a[i]右端点等于t，更新t右端点的开闭性（a[i]和t中有一者为闭则更新t右端点开闭性为闭，否则为开）
				t[3] |= a[i][3];
			//若a[i][1]&lt;t[1]，则不需要改变t
		}
		printf(&quot;%c%d,%d%c\n&quot;, t[2] ? '[' : '(', t[0], t[1], t[3] ? ']' : ')'); //输出本次合并结果
	}
	return 0;
}
</code></pre>
<h3 id="补充">补充</h3>
<p>​	示例代码中用了一些三目运算符和位运算简化了代码，同学们也可以全用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mi>f</mi></mrow><annotation encoding="application/x-tex">if</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">i</span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>e</mi><mi>l</mi><mi>s</mi><mi>e</mi></mrow><annotation encoding="application/x-tex">else</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">s</span><span class="mord mathdefault">e</span></span></span></span> 代替。</p>
<p>​	感兴趣的同学可以去理解一下为什么二维数组排序的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>c</mi><mi>m</mi><mi>p</mi></mrow><annotation encoding="application/x-tex">cmp</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault">m</span><span class="mord mathdefault">p</span></span></span></span> 函数要这么写。</p>
<p><em>Author:</em> 哪吒</p>
<h2 id="i-卡牌大师easy-version"><code>I</code> 卡牌大师(easy version)</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5</td>
<td>链表</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-6">题目分析</h3>
<p>本题的关键在于理解清楚题意并使用链表模拟这一过程。</p>
<p>首先在创建链表时，我们应当创建两个双向循环链表分别表示两人的卡牌序列，在游戏的过程中需要记录下每一轮当前在场上的两张卡牌，当一张卡牌阵亡时，我们执行链表的删除一个元素的操作，当双方其中一方唯一的卡牌阵亡时游戏结束，输出当前的轮数即可。</p>
<p>时间复杂度 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>k</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span> ，注意如果不适用链表而是暴力去删除，时间复杂度将退化到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mo>(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>)</mo><mo>⋅</mo><mi>k</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O((n+m)\cdot k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">m</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span> ，这是不可接受的。</p>
<h3 id="示例代码-1-5">示例代码 1</h3>
<pre><code class="language-cpp">#include&lt;stdio.h&gt;
#define max(a,b) ((a) &gt; (b) ? (a) : (b))
struct node {
	int hp, at, d;
	struct node *nxt;
	struct node *pre;//分别表示链表的前驱和后继
} a[100010], b[100010];//a,b分别表示双方的卡牌序列
int main() {
	int n, m, k;
	scanf(&quot;%d %d %d&quot;, &amp;n, &amp;m, &amp;k);
	for(int i = 0; i &lt; n; i++) {//初始化a链表
		scanf(&quot;%d %d %d&quot;, &amp;a[i].hp, &amp;a[i].at, &amp;a[i].d);
		a[i].nxt = &amp;a[(i + 1) % n], a[i].pre = &amp;a[(i - 1 + n) % n];	
	}
	for(int i = 0; i &lt; m; i++) {//初始化B链表
		scanf(&quot;%d %d %d&quot;, &amp;b[i].hp, &amp;b[i].at, &amp;b[i].d);
		b[i].nxt = &amp;b[(i + 1) % m], b[i].pre = &amp;b[(i - 1 + m) % m];
	}
	struct node *p1 = &amp;a[0], *p2 = &amp;b[0];
	for(int i = 1; i &lt;= k; i++) {
		p2 -&gt; hp = p2 -&gt; hp - max(p1 -&gt; at - p2 -&gt; d, 0);
		p1 = p1 -&gt; nxt;
		if(p2 -&gt; hp &lt;= 0) {//如果当前场上卡牌阵亡
			if(p2 -&gt; nxt == p2) {//是最后一张卡牌时游戏结束
				printf(&quot;+%d&quot;, i);
				return 0;
			} else {//否则删除当前卡牌
				struct node *l = p2 -&gt; pre, *r = p2 -&gt; nxt;
				r -&gt; pre = l, l -&gt; nxt = r;
				p2 = r;
			}
		}
        //同理处理另一边
		p1 -&gt; hp = p1 -&gt; hp - max(p2 -&gt; at - p1 -&gt; d, 0);
		p2 = p2 -&gt; nxt;
		if(p1 -&gt; hp &lt;= 0) {
			if(p1 -&gt; nxt == p1) {
				printf(&quot;-%d&quot;, i);
				return 0;
			} else {
				struct node *l = p1 -&gt; pre, *r = p1 -&gt; nxt;
				r -&gt; pre = l, l -&gt; nxt = r;
				p1 = r;
			}
		}
	}
	printf(&quot;0&quot;);//k轮没结束就是平局
	return 0;
}
</code></pre>
<h3 id="示例代码-2-5">示例代码 2</h3>
<pre><code class="language-c">#include&lt;stdio.h&gt;
#define max(a,b) ((a) &gt; (b) ? (a) : (b))
struct node {
	int hp, at, d;
	int nxt, pre;//分别表示链表的前驱和后继
} a[100010], b[100010];//a,b分别表示双方的卡牌序列
int main() {
	int n, m, k;
	scanf(&quot;%d %d %d&quot;, &amp;n, &amp;m, &amp;k);
	for(int i = 0; i &lt; n; i++) {//初始化a链表
		scanf(&quot;%d %d %d&quot;, &amp;a[i].hp, &amp;a[i].at, &amp;a[i].d);
		a[i].nxt = (i + 1) % n, a[i].pre = (i - 1 + n) % n;	
	}
	for(int i = 0; i &lt; m; i++) {//初始化B链表
		scanf(&quot;%d %d %d&quot;, &amp;b[i].hp, &amp;b[i].at, &amp;b[i].d);
		b[i].nxt = (i + 1) % m, b[i].pre = (i - 1 + m) % m;
	}
	int p1 = 0, p2 = 0;
	for(int i = 1; i &lt;= k; i++) {
		b[p2].hp = b[p2].hp - max(a[p1].at - b[p2].d, 0);
		p1 = a[p1].nxt;
		if(b[p2].hp &lt;= 0) {//如果当前场上卡牌阵亡
			if(b[p2].nxt == p2) {//是最后一张卡牌时游戏结束
				printf(&quot;+%d&quot;, i);
				return 0;
			} else {//否则删除当前卡牌
				int l = b[p2].pre, r = b[p2].nxt;
				b[r].pre = l, b[l].nxt = r;
				p2 = r;
			}
		}
        //同理处理另一边
		a[p1].hp = a[p1].hp - max(b[p2].at - a[p1].d, 0);
		p2 = b[p2].nxt;
		if(a[p1].hp &lt;= 0) {
			if(a[p1].nxt == p1) {
				printf(&quot;-%d&quot;, i);
				return 0;
			} else {
				int l = a[p1].pre, r = a[p1].nxt;
				a[r].pre = l, a[l].nxt = r;
				p1 = r;
			}
		}
	}
	printf(&quot;0&quot;);//k轮没结束就是平局
	return 0;
}
</code></pre>
<h2 id="j-删除子列"><code>J</code> 删除子列</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5~6</td>
<td>贪心、链表</td>
</tr>
</tbody>
</table>
<h3 id="题意分析-3">题意分析</h3>
<p>本题的关键点在于，每次删除子列，删除正整数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置一定是递增的，即第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 次删除时删掉数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置一定大于第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 次删除时删掉数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置。</p>
<p>我们可以建立链表数组，将数列中相同的数的位置用链表存储，即第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 个链表存储的是所有数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置。</p>
<p>然后每次查找子序列时，数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置从上一次找到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置开始，在链表中向后一直遍历到数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 的位置大于本次查找数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">j-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 的位置，若查找成功整个子序列，则删除该数；若查找不成功，则停止查找，直接输出最后的结果。</p>
<p>这样每个数最多只会被遍历一次，时间复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 。</p>
<h3 id="示例代码-1-数组实现链表链式前向星">示例代码 1 - 数组实现链表（链式前向星）</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int n, a[1000005], m, head[100005], tail[100005], next[1000005], flag;
//head[j]表示第j个链表的表头的位置，即第一个j在a中的位置。
//tail[j]表示当前第j个链表的表尾的位置，即当前遍历到的j在a中的位置。
//next[i]表示下一个与ai相同的数的位置
//初始均为0
int main()
{
	scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
	for(int i = 1; i &lt;= n; ++i) //遍历数列a
	{
		scanf(&quot;%d&quot;, &amp;a[i]);
		if(head[a[i]]) //如果链表非空，更新表尾
			tail[a[i]] = next[tail[a[i]]] = i;
		else //否则，创建表头、表尾
			tail[a[i]] = head[a[i]] = i;
	}
	//下面的head[j]表示当前遍历到j的位置，从第一个开始遍历
	while(head[1]) //数1还未被遍历完时
	{
		for(int j = 2; j &lt;= m; ++j)
		{
			while(head[j] &amp;&amp; head[j] &lt; head[j - 1]) head[j] = next[head[j]]; //找到第一个&gt;head[j-1]的head[j]
			if(!head[j])
			{
				flag = 1; //如果head[j]为0，表示未找到，停止查找，退出全部循环
				break;
			}
		}
		if(flag) break;
		for(int j = 1; j &lt;= m; ++j) //成功找到，将该子序列标记为0，并更新head[j]
		{
			a[head[j]] = 0;
			head[j] = next[head[j]];
		}
	}
	for(int i = 1; i &lt;= n; ++i)
		if(a[i]) printf(&quot;%d &quot;, a[i]); //若非0，则未被删掉，输出
	return 0;
}
</code></pre>
<h3 id="示例代码-2-结构体指针实现链表">示例代码 2 - 结构体+指针实现链表</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
typedef struct _node{
	int index; //存储该结点在a中的位置
	struct _node *next; //指向下一个与当前结点相同的数在a中的位置 
} node, *pnode; 
int n, a[1000005], m, flag;
pnode head[100005], tail[100005];
//head[j]存储第j个链表的表头，即第一个数j
//tail[j]表示当前第j个链表的表尾，即当前遍历到的数j
//初始均为0
int main()
{
	scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
	for(int i = 1; i &lt;= n; ++i) //遍历数列a
	{
		scanf(&quot;%d&quot;, &amp;a[i]);
		if(head[a[i]]) //如果链表非空，创建并更新表尾
		{
			tail[a[i]] = tail[a[i]]-&gt;next = (pnode)malloc(sizeof(node));
			tail[a[i]]-&gt;index = i;
			tail[a[i]]-&gt;next = NULL;
		}
		else //否则，创建表头、表尾
		{
			tail[a[i]] = head[a[i]] = (pnode)malloc(sizeof(node));
			head[a[i]]-&gt;index = i;
			head[a[i]]-&gt;next = NULL;
		}
	}
	//下面的head[j]表示当前遍历到j的位置，从第一个开始遍历
	while(head[1]) //数1还未被遍历完时
	{
		for(int j = 2; j &lt;= m; ++j)
		{
			while(head[j] &amp;&amp; head[j]-&gt;index &lt; head[j - 1]-&gt;index) head[j] = head[j]-&gt;next; //找到第一个&gt;head[j-1]的head[j]
			if(!head[j])
			{
				flag = 1; //如果head[j]为空，表示未找到，停止查找，退出全部循环
				break;
			}
		}
		if(flag) break;
		for(int j = 1; j &lt;= m; ++j) //成功找到，将该子序列标记为0，并更新head[j]
		{
			a[head[j]-&gt;index] = 0;
			head[j] = head[j]-&gt;next;
		}
	}
	for(int i = 1; i &lt;= n; ++i)
		if(a[i]) printf(&quot;%d &quot;, a[i]); //若非0，则未被删掉，输出
	return 0;
}
</code></pre>
<p><em>Author:</em> 哪吒</p>
<h1 id="-end-">- End -</h1>
<br />
                                            
                                </p>
                            </div>
                            <div class="post_footer">
                                
                                    <div class="meta">
                                        <div class="info"><span class="field tags"><i class="iconfont icon-tag-sm"></i>
                                                
                                                    <a href="https://github.pansis.site/tag/24hc/" class="article-info">
                                                        23航C
                                                    </a>
                                                    
                                            </span>
                                        </div>
                                    </div>
                                    
                                        
                            </div>
                        </div>
                        
                            
                                <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id="gitalk-container" style="padding-bottom: 20px;"></div>
<script>
    var pageId = (location.pathname).substring(1, 49) // Ensure uniqueness and length less than 50
    pageId = pageId.endsWith('/') ? pageId.slice(0, -1) : pageId // 以斜杠结尾则去除
    var gitalk = new Gitalk({
        clientID: '9d5eba33618472c44a07',
        clientSecret: '065a85ed04333ceebfc4f01d7ca1674175730339',
        repo: 'fzxl2003.github.io',
        owner: 'fzxl2003',
        admin: ['fzxl2003'],
        id: pageId,
        distractionFreeMode: false  // Facebook-like distraction free mode
    })
    gitalk.render('gitalk-container')
</script>
                                    
                                        
                                                    
                    </div>
                </div>
            </div>
    </div>
    <div class="footer">
    
    <div class="powered_by">
        <a href="https://codeberg.org/kytrun/gridea-theme-one" target="_blank">Theme One,</a>
        <a href="https://open.gridea.dev/" target="_blank">Powered by Gridea&#65281;</a>
    </div>
    
    
        <div class="footer_slogan">
            Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a>
        </div>
    
    <div id="back_to_top" class="back_to_top">
        <span>△</span>
    </div>
    
</div>

<script src="https://github.pansis.site/media/scripts/util.js"></script>
        <link rel="stylesheet" href="//unpkg.com/@highlightjs/cdn-assets@11.5.1/styles/default.min.css">
        <script src="//unpkg.com/@highlightjs/cdn-assets@11.5.1/highlight.min.js"></script>
        <script>hljs.highlightAll();</script>
</body>

</html>